package main

import (
	"fmt"
	"math/rand"
)

func main() {
	//obj := Constructor()
	//param_1 := obj.Insert(1)
	//param_2 := obj.Remove(2)
	//param_3 := obj.GetRandom()
	//fmt.Println(param_1, param_2, param_3)

	opList := []string{"RandomizedSet", "insert", "insert", "remove", "insert", "remove", "getRandom"}
	opDataList := [][]int{{}, {0}, {1}, {0}, {2}, {1}, {}}
	expectList := []interface{}{nil, true, true, true, true, true, 2}

	var instance RandomizedSet
	for i, op := range opList {
		switch op {
		case "RandomizedSet":
			instance = Constructor()
		case "insert":
			res := instance.Insert(opDataList[i][0])
			if res != expectList[i] {
				fmt.Println("insert error")
			}
		case "remove":
			res := instance.Remove(opDataList[i][0])
			if res != expectList[i] {
				fmt.Println("remove error")
			}
		case "getRandom":
			res := instance.GetRandom()
			fmt.Println(res)
		}
	}
}

// RandomizedSet 380  O(1) 时间插入、删除和获取随机元素
// o1 插入和删除一定是链表，但是链表查找是O(N)
// 随机获取 O1 应该是数组
type RandomizedSet struct {
	valSet []int
	point  map[int]int
}

func Constructor() RandomizedSet {
	size := 10
	return RandomizedSet{
		valSet: make([]int, 0, size),
		point:  make(map[int]int, size),
	}
}

func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.point[val]; ok {
		return false //存在返回false
	}

	this.valSet = append(this.valSet, val)
	this.point[val] = len(this.valSet) - 1
	return true
}

func (this *RandomizedSet) Remove(val int) bool {
	pos, ok := this.point[val]
	if !ok {
		return false
	}

	endPos := len(this.valSet) - 1
	// replace with the end element
	if pos != endPos {
		endElement := this.valSet[endPos]
		this.valSet[pos] = endElement
		this.point[endElement] = pos
	}
	delete(this.point, val)
	this.valSet = this.valSet[0:endPos]
	return true
}

func (this *RandomizedSet) GetRandom() int {
	l := len(this.valSet)
	p := rand.Intn(l)
	return this.valSet[p]
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */
